/*
 * @lc app=leetcode.cn id=483 lang=typescript
 *
 * [483] 最小好进制
 */

// @lc code=start
function smallestGoodBase(n: string): string {
  let num = Number(n);
  // 最多的位数就是2进制的位数
  const max = Math.floor(Math.log(num) / Math.log(2));

  for (let i = max; i > 1; i--) {
    let k = BigInt(Math.floor(Math.pow(num, 1 / i)));
    if (k > 1) {
      let cur = 1n;
      let sum = 1n;
      for (let j = 1; j <= i; j++) {
        cur *= k;
        sum += cur;
      }
      if (sum === BigInt(n)) {
        return String(k);
      }
    }
  }

  return String(BigInt(n) - 1n);
}
// @lc code=end
